package sort.advanced_sort;

import org.junit.Test;

import java.util.Arrays;

public class Demo1_MergeSort {
    /**
     * 归并排序
     *
     * 算法思想：二分 + 合并
     *
     * 对于一个数组来说：{6, 13, 1, 90, 324, 79, 34, 66};
     * 找到其中点，分成左右两部分，直到不能分割为止
     * 第一次二分：{6, 13, 1, 90} 和 {324, 79, 34, 66};
     * 第二次二分：{6, 13}、{1, 90}、{324, 79}、{34, 66};
     * 第三次二分：{6} {13} {1} {90} {324} {79} {34} {66};
     *
     * 然后进行比较合并。
     *
     */
    /**
     * 利用辅助数组的方式进行归并排序(in - place),利用额外空间对原数组进行修改。
     *
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        //无效判断也可以在主函数中或调用函数中进行。
        if (arr == null || arr.length < 2) {
            return;
        }
        //开辟一个辅助数组
        int[] helper = new int[arr.length];
        //对li = 0, hi = arr.length - 1 进行分治
        sort(arr, helper, 0, arr.length - 1);
    }

    public static void sort(int[] arr, int[] helper, int lo, int hi) {
        //base case 递归出口
        if (lo >= hi) {
            return;
        }
        //中点
        int mid = lo + (hi - lo) / 2;
        //中点左边分一下
        sort(arr, helper, lo, mid);
        //中点右边分一下
        sort(arr, helper, mid + 1, hi);
        /*
            优化点1：如果后一部分的最小值 > 前一部分的最大值，此时数组已经有序，直接返回

            （完整排序才能使用，自定义排序会有问题）
         */
        if (arr[mid + 1] > arr[mid]) {
            return;
        }
        //合并
        merge(arr, helper, lo, mid, hi);
    }

    public static void merge(int[] arr, int[] helper, int lo, int mid, int hi) {
        //将原数组拷贝到辅助数组
        for (int i = lo; i <= hi; i++) {
            helper[i] = arr[i];
        }
        /*
            leftIndex 指针从分治后的 辅助数组左数组 第一个索引位置开始 rightIndex从右数组第一个位置开始

            比如原数组数组：   {6, 13, 1, 90}，
                             0,  1, 2,  3
            拷贝数组：        {6, 13, 1, 90}

            leftIndex(0)位置值为6  rightIndex(2)位置值为1

            6 和 1 进行比较，将1放回原数组的k(0) 位置，然后rightIndex++, k++ 此时原数组{1,13,1,90}
            6 和 90进行比较，将6放回原数组的k(1) 位置，然后leftIndex++, k++ 此时原数组{1,6,13,90} leftIndex = 1, rightIndex = 1;
            13 和 90进行比较，将13放回原数组k(2) 位置，然后leftIndex++, k++ 此时原数组{1,6,13,90} leftIndex = 2, rightIndex = 1;

            此时leftIndex = 2  > mid = 1越界，直接将右部分剩余元素放回原数组即可。
         */
        int leftIndex = lo, rightIndex = mid + 1;
        for (int k = lo; k <= hi; k++) {
            //左边的数组越界
            if (leftIndex > mid) {
                arr[k] = helper[rightIndex++];
            } else if (rightIndex > hi) {
                arr[k] = helper[leftIndex++];
            } else if (helper[leftIndex] > helper[rightIndex]) {
                arr[k] = helper[rightIndex++];
            } else {
                arr[k] = helper[leftIndex++];
            }
        }
    }


    /**
     * 自底向上的归并排序
     *
     * @param arr
     */
    public static void bottomToUpMergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int N = arr.length;
        int[] helper = new int[N];
        for (int len = 1; len < N; len = len << 1) {
            //前进len << 1步
            for (int leftIndex = 0; leftIndex < N - len; leftIndex = leftIndex + (len << 1)) {
                int mid = leftIndex + len - 1;
                int rightIndex = Math.min(leftIndex + (len << 1) - 1, N - 1);
                merge(arr, helper, leftIndex, mid, rightIndex);
            }
        }
    }

    // for test
    public static void comparator(int[] arr) {
        Arrays.sort(arr);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    // for test
    public static void main(String[] args) {
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            mergeSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        mergeSort(arr);
        printArray(arr);
    }
    @Test
    public void test(){
        int testTime = 500000;
        int maxSize = 100;
        int maxValue = 100;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            int[] arr2 = copyArray(arr1);
            bottomToUpMergeSort(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
        }
        System.out.println(succeed ? "Nice!" : "Fucking fucked!");

        int[] arr = generateRandomArray(maxSize, maxValue);
        printArray(arr);
        bottomToUpMergeSort(arr);
        printArray(arr);
    }
}
